The invention relates to a technique for optimizing code. More specifically, a method, computer, computer program, and computer program product for preventing under certain conditions the invalidation of compiled code that has been optimized.
Programming languages with local variables, global variables, local functions, and global functions are known to behave so that some global variables or functions are updated less frequently than other variables and functions including local variables as described in Alex Holkner et al., “Evaluating the dynamic behaviour of Python applications.”, In Proceedings of the Thirty-Second Australasian Conference on Computer Science, Volume 91, pp. 19-28, 2009.
This behavior can be used to establish global variables or functions as constant values during compiling, speculatively optimize code including these constant values, execute compiled code including this optimized code, and invalidate compiled code when there is a possibility that these constant values will be changed during execution as described in “Issue 109043: Optimize LOAD_GLOBAL—Code Review”.
The Python language can be run on most operating systems such as Linux®, Mac OS X®, and Windows®. Python has a proven track record at Google® and the National Aeronautics and Space Administration (NASA). As a result, Python is expected to become increasingly popular among users worldwide.
The search order in the lexical scope of the Python language is as follows: local variables, outside functions, global variables or functions, and then built-in variables or functions as described in “9.2. Python Scopes and Namespaces”, Python v2.7.3.
A lexical scope is also called a static scope, and is a method using only a scope that can be determined syntactically. Searches in this order, that is, searches in the order of a global variable or function dictionary followed by a built-in variable or function dictionary, are performed by a single byte code instruction (LOAD_GLOBAL) as described in “Python hacking using dis/inspect module and ceval.c”.
Therefore, when this invalidation technique is applied to the LOAD_GLOBAL instruction, speculative optimization can be performed to two cases of optimization: (1) rendering the values of global variables or functions constant (known as “constant propagation”), and (2) static determination of the callees for built-in variables or functions and code specialization (known as “code specialization”). On the other hand, compiled code is invalidated when a dictionary of global variables or functions or a dictionary of built-in variables or functions related to compiled code is updated as described in “Issue 109043: Optimize LOAD_GLOBAL-Code Review” reference.
In Python, an exec statement supports the dynamic execution of Python code. Any statement can be executed by an exec statement with given dictionaries of global variables or functions as described in “6.14 The exec statement”, Python Reference Manual.
Therefore, because there is a possibility that a constant value will be updated when an address update is performed for given dictionaries of global variables or functions, compiled code that has been optimized is invalidated.
Patent Publication No. 2005-215830 discloses an optimization compiler which includes an update instruction detecting unit for detecting, in a program to be optimized, an update instruction for updating the content of a variable or the content of a storage area specified by a variable; an instruction sequence detecting unit for detecting, in a program to be optimized, an instruction sequence transferring control in response to a control transferring instruction for transferring control to another instruction sequence, and performing processing depending on the content of the variable or the content of the storage area; an instruction sequence compiler for optimizing and compiling the detected instruction sequence in processing for situations in which the content of the variable or the content of the storage area is specific predetermined content; and a setting instruction generating unit executed on a program to be optimized between the updating instruction and the control transferring instruction in situations in which the content of the variable or the content of the storage area is specific predetermined content, and generating a setting instruction for setting the destination address in the control transferring instruction for the address of the instruction sequence optimized by the instruction sequence compiling unit. In other words, in Patent Publication No. 2005-215830, the presence of any updates in a plurality of storage areas such as variables and array is detected, and an operation such as compiling is performed again.
Patent Publication No. 2008-102748 describes a program executing method, language processing system, and run-time routine able to avoid optimization suppression caused by a function which overwrites a variable value via the variable name, thereby speeding up execution of a program. In a computer system with a storage unit and a processing unit, the program executing method executes a program to be executed stored in the storage unit using a program for a language processing system stored in the storage unit.
In this language processing method, the program to be executed is optimized using a dynamic compiler for the language processing system on the assumption that the value of a variable stored in a predetermined area of the storage unit is immutable. The run-time routine of the language processing system is used to monitor whether or not the predetermined area in the program to be executed has been overwritten via the variable name corresponding to the predetermined area. When there is a possibility that an overwrite has occurred, the code optimized by the dynamic compiler on the assumption that the value of the variable stored in the predetermined area of the storage unit was immutable is invalidated. In other words, in Patent Publication No. 2008-102748, a decision whether or not to invalidate optimized code is made based on which value belonging to a set of variables has been overwritten.
When all dictionaries of global variables and functions and all dictionaries of built-in variables and functions are monitored, that is, when all dictionaries and all keys and values in these dictionaries are monitored, and a key or value is changed, an opportunity to perform speculative optimization is not lost if the compiled code associated with the changed dictionary is invalidated. However, monitoring and invalidating changes in all dictionaries is too costly and impractical.
In Issue 109043: Optimize LOAD_GLOBAL-Code Review” reference, whenever a dictionary of global variables or functions or a dictionary of built-in variables or functions is updated in some implementations of the Python language, compiled code is invalidated no matter which key or value was changed. However, this does not take into account the fact that invalidation of compiled code is not required when a dictionary is updated under certain conditions. As a result, the invalidation methods described above lose opportunities to improve performance.
Also, whenever the address for a dictionary of global variables or functions passed to the code is updated in some implementations of the Python language, the compiled code is always invalidated as described in “Issue 109043: Optimize LOAD_GLOBAL-Code Review” reference. However, this does not take into account the fact that invalidation of compiled code is not required when an address is updated under certain conditions. As a result, the invalidation methods described above lose opportunities to improve performance.
Therefore, the purpose of the present invention is to prevent invalidation when the invalidation of compiled code is not required, thereby improving performance.